#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int p;
ll qpow(ll base,ll exp){
    ll ans=1;
    while(exp){
        if(exp&1) ans=ans*base%p;
        base=base*base%p;
        exp>>=1;
    }
    return ans;
}

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b){
        ll ans=exgcd(b,a%b,x,y);
        ll t=x;x=y;y=t-a/b*y;
        return ans;
    }else{
        x=1;y=0;
        return a;
    }
}

ll ine(ll a,ll b=1){
    ll x,y;
    a%=p;b%=p;
    ll g=exgcd(a,p,x,y);
    if(b%g) return -2;
    x*=b/g;
    return (x%p+p)%p;
}

int bsgs(ll base,ll val){
    int m=ceil(sqrt(p));
    if(base==0&&val==0) return 1;
    else if(base==0) return -1;
    base%=p;val%=p;
    map<int,int> ha;
    ll t=1;
    for(int i=0;i<m;i++,t=t*base%p) if(!ha.count((int)t)) ha[(int)t]=i;
    t=qpow(base,p-1-m);
    ll q=val;
    for(int k=0;k<=m;k++){
        if(ha.count(q)) return k*m+ha[q];
        q=q*t%p;
    }
    return -2;
}

inline int read(){
    char c;int r;bool f=0;
    for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') f=1;
    for(r=0;c<='9'&&c>='0';c=getchar()) r=r*10+c-'0';
    if(f) return -r;
    else return r;
}

int main(){
    int T,a,b,x1,t;

    T=read();
    while(T--){
        p=read();a=read();b=read();x1=read();t=read();
        if(x1==t) printf("1\n");
        else if(a==0){
            if(t==b) printf("2\n");
            else printf("-1\n");
        }else if(a==1){
            printf("%d\n",(int)ine(b,t-x1)+1);
        }else{
            ll c=b*ine(a-1)%p;
            printf("%d\n",bsgs(a,(t+c)*ine(x1+c)%p)+1);
        }
    }
    return 0;
}
